package HelloAlgo.LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author jing
 * @BelongsProject: JavaDataStructure
 * @CreateTime: 2025-03-08  20:44
 * @Description:
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * @Version: 1.0
 */
public class Code70 {
    public static void main(String[] args) {
        System.out.println(climbStairs1(5));
        System.out.println(climbStairs2(5));
    }

    //循环+递归
    public  static int climbStairs1(int n){
        if(n == 1){
            return  1;
        }
        if(n == 2){
            return 2;
        }
        int result = 0;
        int pre = 2;
        int prepre = 1;
        for(int i = 3;i<=n;i++){
            result = pre+prepre;
            prepre = pre;
            pre = result;
        }
        return result;
    }

    //使用HashMap
    public static int climbStairs2(int n) {
        Map<Integer,Integer> map = new HashMap<>();
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(null != map.get(n)){
            return map.get(n);
        }else {
            int result = climbStairs2(n-1)+climbStairs2(n-2);
            map.put(n,result);
            return result;
        }
    }

}
